#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // vector<int> maxSlidingWindow(vector<int> &nums, int k)
    // {
    //     queue<int> que;
    //     vector<int> res;
    //     for (auto num : nums)
    //     {
    //         if (que.size() < (size_t)k)
    //         {
    //             que.push(num);
    //         }
    //         if (que.size() == (size_t)k)
    //         {
    //             queue<int> copy_que;
    //             copy_que = que;
    //             int max = INT_MIN;
    //             while (!copy_que.empty())
    //             {
    //                 if (copy_que.front() > max)
    //                 {
    //                     max = copy_que.front();
    //                 }
    //                 copy_que.pop();
    //             }
    //             res.push_back(max);
    //             que.pop();
    //         }
    //     }
    //     return res;
    // }

    // vector<int> maxSlidingWindow(vector<int> &nums, int k)
    // {
    //     vector<int> res;
    //     deque<int> que;
    //     int length = nums.size();
    //     for (int i = 0; i < length; i++)
    //     {
    //         if (!que.empty() && que.front() == i - k)
    //         {
    //             que.pop_front();
    //         }
    //         while (!que.empty() && nums[i] > nums[que.back()])
    //         {
    //             que.pop_back();
    //         }
    //         que.push_back(i);
    //         if (i >= k - 1)
    //         {
    //             res.push_back(nums[que.front()]);
    //         }
    //     }
    //     return res;
    // }

    // vector<int> maxSlidingWindow(vector<int> &nums, int k)
    // {
    //     vector<int> res;
    //     priority_queue<pair<int, int>> que;
    //     int length = nums.size();
    //     for (int i = 0; i < length; i++)
    //     {
    //         que.push(pair(nums[i], i));
    //         if (i + 1 >= k)
    //         {
    //             while (!que.empty() && que.top().second <= i - k)
    //             {
    //                 que.pop();
    //             }
    //             res.push_back(que.top().first);
    //         }
    //     }
    //     return res;
    // }

    // vector<int> maxSlidingWindow(vector<int> &nums, int k)
    // {
    //     multiset<int> set;
    //     vector<int> res;
    //     int length = nums.size();
    //     for (int i = 0; i < length; i++)
    //     {
    //         set.insert(nums[i]);
    //         if (i >= k - 1)
    //         {
    //             res.push_back(*set.rbegin());
    //             set.erase(set.find(nums[i - k + 1]));
    //         }
    //     }
    //     return res;
    // }

    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> res;
        int length = nums.size();
        for (int i = 0; i < length; i++)
        {
            if (i >= k)
            {
                pop(nums[i - k]);
            }
            push(nums[i]);
            if (i >= k - 1)
            {
                res.push_back(get_max());
            }
        }
        return res;
    }

public:
    void push(int value)
    {
        while (!que.empty() && value > que.back())
        {
            que.pop_back();
        }
        que.push_back(value);
    }
    void pop(int value)
    {
        if (que.front() == value)
        {
            que.pop_front();
        }
    }
    int get_max()
    {
        return que.front();
    }

public:
    deque<int> que;
};

int main()
{
    vector<int> vec{1, 3, -1, -3, 5, 3, 6, 7};
    Solution sol;
    vector<int> res = sol.maxSlidingWindow(vec, 3);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}